#!/usr/env/bin python
# -*- coding: utf-8 -*-

# @Time    : 2020-09-03 11:35 上午
# @Author  : yangdy
# @File    : 2020-09-03.51.N皇后
# @Software: PyCharmCE
from tools.my_methods import *


class Solution:
    def solveNQueens(self, n: int) -> List[List[str]]:
        ans = []
        if n <= 0:
            return ans
        pos = [-1 for i in range(n)]

        def check(_i, _r):
            for i in range(_r):
                if _i == pos[i] or (_r - i == abs(_i - pos[i])):
                    return False
            return True

        def dfs(row, nn):
            if row >= nn:
                ret = []
                for i in pos:
                    ret.append('.' * i + 'Q' + '.' * (nn - i - 1))
                ans.append(ret)
                return
            for i in range(n):
                if check(i, row):
                    pos[row] = i
                    dfs(row+1, nn)
                    pos[row] = -1

        dfs(0, n)

        return ans


questions = [
    (4, ),
]

work(questions, lambda q: Solution().solveNQueens(q[0]))
